package mf.trees.preorder_all;

import java.io.File;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

import mf.tools.Command;
import mf.trees.Rule;
import mf.trees.SLTreeGrammar;

@SuppressWarnings("unchecked")
/**
 * TreeModel. Represents the tree grammar defined by File <b>f</b> and
 * the mappings L and R.
 * 
 * @author Maik Funkat
 */
public class TreeModel {
	
	//debug mode displays more informations
	private boolean DEBUG_MODE = false;
	
	//Tree grammar
	private SLTreeGrammar gr;
	
	//Stack for traversing the tree
	private Stack<Command> T = new Stack<Command>();

	//ArrayLists for left derivations
	private ArrayList<Integer> L[];
	//ArrayLists for right derivations
	private ArrayList<Integer> R[];

	//starting variable
	private int S = 0;
	
	//current node
	private String currentNode = "0";

	//size table
	private Integer treesize[];
	//preorder number
	private int preorder = 0;
	
	/** Construct a new tree model.*/
	public TreeModel(File f, boolean d) {
		DEBUG_MODE = d;
		
		//load grammar file
		gr = new SLTreeGrammar(f);
		
		debug("Loading file " + f.getAbsolutePath() + "\n\n" +
			  "Rules:\n" + gr.toString()
		);
		
		//initialize mappings
		L = new ArrayList[gr.size()];
		R = new ArrayList[gr.size()];
		
		//preprocess maps
		preprocessMaps();
		
		//initialize tree size table
		treesize = new Integer[gr.size()];
		treesize(0);
		
		//initialize stack
		T.push(new Command(S, H(S), Command.LEFT_DIRECTION));
		T.push(new Command(L(S, H(S)), treesize(0), Command.UP_DIRECTION));
		
		debug("preprocess mappings...\n"+
			  "L = "+Arrays.toString(L)+"\n"+
			  "R = "+Arrays.toString(R)+"\n\n"+
			  "treesize table = "+Arrays.toString(treesize) +"\n"
		);
	}

	/** Calculate mappings L, R and U. */
	private void preprocessMaps() {
		//in the first run, we save the direct descendants
		for(int i=0; i<gr.size(); i++) {
			Rule r = gr.getRule(i);

			ArrayList<Integer> L_i = new ArrayList<Integer>();
			ArrayList<Integer> R_i = new ArrayList<Integer>();

			if(!r.isType2()) {
				L_i.add(r.child(0));
				R_i.add(r.child(1));
			}
			
			L[i] = L_i;
			R[i] = R_i;
		}

		//in the second run, we collect all left and right derivations
		for(int i=0; i<gr.size(); i++) {
			if(L[i].size() != 0) {
				ArrayList<Integer> tmp = L[L[i].get(0).intValue()];
				
				while(true) {
					if(tmp.size() == 0)
						break;

					L[i].add(tmp.get(0));
					tmp = L[tmp.get(0)];
				}
			}
			if(R[i].size() != 0) {
				ArrayList<Integer> tmp = R[R[i].get(0).intValue()];
				
				while(true) {
					if(tmp.size() == 0)
						break;

					R[i].add(tmp.get(0));
					tmp = R[tmp.get(0)];
				}
			}
		}
	}
	
	/** Calculate the tree size table of a straight-line tree grammar. */
	private int treesize(int i) {
		//if value is known, return it
		if (treesize[i] != null)
			return treesize[i];
		
		//else get the corresponding rule
		Rule r = gr.getRule(i);
		
		//if it is type 1
		if(!r.isType2())
			return (treesize[i] = treesize(r.child(0)) + treesize(r.child(1)));
		else {
			int s = 1;
			
			//add up children sizes except if children is x
			for(int j=0; j<r.childs(); j++)
				if(r.child(j).intValue() != 0) 
					s += treesize(r.child(j));
			
			return (treesize[i] = s);
		}
	}
	
	/** Navigate to the i-th son. */
	public void gotoSon(int i) {
		Command top = T.peek();
		Rule rule = gr.getRule(top.variable());
		
		//if i is not valid, i.e. node has less than i sons
		if(0 == rule.childs() || rule.childs() <= i) {
			debug("Node has no child #"+(i+1)+"!");
			return;
		}

		//calculate the sizes of the child subtrees
		int fatherSize = top.length(),
			xIndex = -1,
			sum = 0,
			childsize[] = new int[rule.childs()];
		
		for(int j=0; j<rule.childs(); j++)
			if(rule.child(j) > 0) {
				sum += (childsize[j] = treesize(rule.child(j)));
			} else
				xIndex = j;
		childsize[xIndex] = fatherSize - sum - 1;
		
		//calculate the new preorder number
		preorder += 1;
		for(int j=0; j<i; j++)
			preorder += childsize[j];
		
		//if the i-th son is x, we must find it
		if(rule.child(i).intValue() == 0) 
			gotoSonX(childsize[xIndex]);
		//else son i is a nonterminal B, so we follow B
		else	
			gotoSonB(rule.child(i));

		//update current node 
		currentNode += "."+(i+1);
	}
	
	/** Navigate to the i-th son which is a nonterminal B. */
	private void gotoSonB(Integer B) {
		Integer k = H(B);
		
		//add maximal left chain starting at A_i (can be zero) and one up-step
		if(k.intValue() > -1) {
			T.push(new Command(B, k, Command.LEFT_DIRECTION));
			T.push(new Command(L(B, k.intValue()), treesize(B), Command.UP_DIRECTION));
		} else
			T.push(new Command(B, treesize(B), Command.UP_DIRECTION));
	}
	
	/** Navigate to the i-th son which is an unknown variable x. */
	private void gotoSonX(int s) {
		//delete U-step
		T.pop();
		
		//delete possible right chains
		if(T.peek().direction().intValue() == Command.RIGHT_DIRECTION)
			T.pop();
		
		//next stack element must be of form (A, i, L)
		Command lChain = T.pop();
		System.out.println(lChain.toString());
		Integer Y = lChain.variable(), ell = 0;
		
		//if i > 0, reduce length of left chain by 1
		if(lChain.length().intValue() > 0) {
			T.push(new Command(lChain.variable(), lChain.length()-1, lChain.direction()));
			
			Y = L(lChain.variable(), lChain.length()-1);
		} else	//look for preceding right chain
			if(!T.isEmpty())
				if(T.peek().direction().intValue() == Command.RIGHT_DIRECTION) {
					Command rChain = T.pop();
				
					Y = rChain.variable();
					ell = rChain.length() + 1;
				}
		
		//done right step(s)
		T.push(new Command(Y, ell, Command.RIGHT_DIRECTION));
		
		//do maximal left step (can be zero) and one up step
		Y = R(Y, ell);
		Integer k = H(Y);
		
		//maximal left step plus up step
		if(k.intValue() > -1) {
			T.push(new Command(Y, k, Command.LEFT_DIRECTION));
			T.push(new Command(L(Y, k.intValue()), s, Command.UP_DIRECTION));
		} else  //just one up step
			T.push(new Command(Y, s, Command.UP_DIRECTION));
	}
	
	/** Navigate to the father node of the current node. */
	public void gotoFatherNode() {
		// delete U-Step
		Command top = T.pop();
		int nodeSize = top.length();
		
		// check for grammar root
		if (T.peek().equals(S, H(S), Command.LEFT_DIRECTION)) {
			T.push(top);
			
			debug("The root has no father!");
			return;
		}

		// delete left chain if existent
		if (T.peek().direction().intValue() == Command.LEFT_DIRECTION)
			T.pop();

		//if next top stack is an U-step, we have found the father
		Command rChain = T.pop();
		if (rChain.direction().intValue() == Command.UP_DIRECTION) {
			//calculate child sizes: we know the size of the father, so we know the size of all children except x. but size(x) = size(father) - size(all other children) - 1
			Rule rule = gr.getRule(rChain.variable());
			int dotPos = currentNode.lastIndexOf(".")+1,
				childNr = Integer.parseInt(currentNode.substring(dotPos))-1,
				fatherSize = rChain.length().intValue(),
				xIndex = -1,
				sum = 0,
				childsize[] = new int[rule.childs()];;
			
			for(int j=0; j<rule.childs(); j++)
				if(rule.child(j) > 0) {
					sum += (childsize[j] = treesize(rule.child(j)));
				} else
					xIndex = j;
			
			childsize[xIndex] = fatherSize - sum - 1;
			
			debug("Father has size "+ fatherSize + " and rule " + rule.toString() + "\n"+
				  "children have sizes " + Arrays.toString(childsize) +
				  " with childsize[xIndex="+childNr+"] = "+childsize[childNr] +"\n"
			);
			
			//calculate new preorder
			preorder -= 1;
			for(int j=0; j<childNr; j++)
				preorder -= childsize[j];
			
			//push father
			T.push(rChain);
		} else {// else the next top stack must be a right chain
			Integer Y = rChain.variable();
			
			// so decrement if possible
			if (rChain.length().intValue() > 0) {
				T.push(new Command(rChain.variable(), rChain.length() - 1,
						rChain.direction()));
				Y = R(rChain.variable(), rChain.length() - 1);
			}

			//check for existing left chain
			Integer ell = 0;
			if (!T.isEmpty()) {
				if (T.peek().direction().intValue() == Command.LEFT_DIRECTION) {
					Y = T.peek().variable();
					ell = T.pop().length() + 1;
				}
			}
			//and do one more left step
			T.push(new Command(Y, ell, Command.LEFT_DIRECTION));
			Y = L(Y, ell);

			// do maximum right chain
			if (W(Y) > -1) {
				T.push(new Command(Y, W(Y), Command.RIGHT_DIRECTION));
				Y = R(Y, W(Y));
			}
			
			//calculate childsizes and fathersize: we dont know the size of the father, but its rule. so we know the size of his children, and especially the size(x) = nodeSize.
			Rule rule = gr.getRule(Y);
			int dotPos = currentNode.lastIndexOf(".")+1,
				childNr = Integer.parseInt(currentNode.substring(dotPos))-1,
				sum = 0,
				childsize[] = new int[rule.childs()];;
		
			for(int j=0; j<rule.childs(); j++)
				if(rule.child(j) > 0) {
					sum += (childsize[j] = treesize(rule.child(j)));
				} else
					sum += (childsize[j] = nodeSize);
			
			debug("Father has size "+ (sum+1) + " and rule " + rule.toString() + "\n"+
				  "children have sizes " + Arrays.toString(childsize) +
				  " with childsize[xIndex="+childNr+"] = "+childsize[childNr] +"\n"
			);
			
			//calculate new preorder
			preorder -= 1;
			for(int j=0; j<childNr; j++)
				preorder -= childsize[j];


			//push father
			T.push(new Command(Y, sum+1, Command.UP_DIRECTION));
		}
		
		currentNode = currentNode.substring(0, currentNode.lastIndexOf("."));
	}
	
	/** Access to the j-th element of the left derivations of non-terminal A_i. */
	private Integer L(int i, int j) {
		System.out.print("get L_{"+j+"/"+L[i].size() + "]("+i+")\n");
		return L[i].get(j);
	}

	/** Length of the left derivations of non-terminal A_i. */
	private Integer H(int i) {
		return L[i].size() - 1;
	}

	/** Access to the j-th element of the right derivations of non-terminal A_i. */
	private Integer R(int i, int j) {
		return R[i].get(j);
	}

	/** Length of the right derivations of non-terminal A_i. */
	private Integer W(int i) {
		return R[i].size() - 1;
	}

	/** Returns true if debug mode is set. */
	public boolean debugMode() {
		return DEBUG_MODE;
	}
	
	/** Returns the label of the node the stack points at. */
	public String getNodeLabel() {
		if(T.isEmpty())
			return "Error: no tree found.";
		
		Command top = T.peek();
		Rule r = gr.getRule(top.variable());
		int size = top.length().intValue();
		
		return
			"current node: " + formatNode(currentNode) + "\n" +
			"label: "+ r.label() + "\n"+
			"childrens: " + r.childs() + "\n"+
			"size of subtree: "+ size + "\n"+
			"preorder number: " + preorder + "\n";
	}
	
	/** Formats the current node. */
	private String formatNode(String c) {
		return c.equals("0") ? c : c.substring(2);
	}

	/** Get debug informations. */
	public String getDebugText() {
		if(DEBUG_MODE) {
			Command top = T.peek();
			Rule r = gr.getRule(top.variable());
			
			return
				"<html><body>"+
				"Grammar has " +gr.size() + " rules.<br />"+
				"Stack T = " + T.toString() + " with top rule " +
				"A_" + top.variable() + 
				(r.childs() == 0 ? "" : "(x)") +
				" -> " + r + "\n" +
				"</body></html>";
		}
		return "";
	}
	
	/** Resets the stack. It then points at the root of the tree. */
	public void resetStack() {
		T.clear();
		T.push(new Command(S, H(S), Command.LEFT_DIRECTION));
		T.push(new Command(L(S, H(S)), treesize(0), Command.UP_DIRECTION));
		currentNode = "0";
		preorder = 0;
		
		debug("Stack resetted..\n");
	}
	
	/** Prints debug notes on debug mode. */
	private void debug(String s) {
		if(DEBUG_MODE)
			System.out.println(s);
	}
}